#pragma once 
#include<iostream>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

namespace sz
{
  template<class T>
  class vector 
  {
    public:
      typedef T* iterator;
      typedef const T* const_iterator;
      
      iterator begin()
      {
        return _start;
      }
      iterator end()
      {
        return _finish; 
      }

      const_iterator begin() const 
      {
        return _start;
      }
      const_iterator end() const 
      {
        return _finish; 
      }

      T& operator[](size_t pos)
      {
        assert(pos < size());
        return _start[pos];
      }
      T& operator[](size_t pos) const 
      {

        assert(pos < size());
        return _start[pos];
      }


      vector()
        :_start(NULL) 
        ,_finish(NULL)
        ,_end_of_storage(NULL)
      {}
      
      vector(size_t n, const T& val = T())
        :_start(NULL)
        ,_finish(NULL)
        ,_end_of_storage(NULL)
      {
        for(size_t i = 0; i< n; i++)
        {
          push_back(val);
        }
      }

      vector(int n, const T& val = T())
        :_start(NULL)
        ,_finish(NULL)
        ,_end_of_storage(NULL)
      {
        for(size_t i = 0; i< n; i++)
        {
          push_back(val);
        }
      }
     
      template<class Inputiterator>
      vector(Inputiterator first, Inputiterator last)
      {
        while(*first != last)
        {
          push_bakc(*first);
          first++;
        }
      }

      vector(const vector<T>& v)
        :_start(NULL)
        ,_finish(NULL)
        ,_end_of_storage(NULL)
      {
        _start = new T[v.size()];
        memcpy(_start,v._start, sizeof(T)*v.size());
        _finish = _start + v.size(); 
        _end_of_storage = _finish;
      }

      vector<T>& operator=(vector<T> v)
      {
        swap(v);
        return *this;
      }
      ~vector()
      {
        delete[] _start;
        _start = _finish = _end_of_storage = NULL; 
      }
      // 扩容
      size_t size() const 
      {
        return _finish - _start;  
      }
      size_t capacity() const 
      {
        return _end_of_storage - _start; 
      }
      
      T& front()
      {
        assert(size() > 0);
        return *_start;
      }
      T& back()
      {
        assert(size() > 0);
        return *(_finish - 1);
      }
      void reverse(size_t n)
      {
        if(n > capacity())
        {
          size_t len = size(); 
          T* tmp = new T[n];
          // _start非空
          if(_start)
          {
             memcpy(tmp, _start, sizeof(T)* len);
             delete[] _start;
          }
             _start = tmp;
             _finish = _start + len;
             _end_of_storage = _start + n;
        }
      }
      void resize(size_t n, const T& val = T())
      {
        if(n > capacity())
        {
          reverse(n);
        }
        if(n> size())
        {
          while(_finish < _start + n)
          {
            *_finish = val;
            _finish++;
          }
        }
        else 
        {
          _finish = n;
        }
      }
      // 功能
      void push_back(const T& x)
      {
        if(_finish == _end_of_storage)
        {
          reverse(capacity() == 0 ? 4 : capacity() * 2);
        }
        *_finish = x;
        _finish++;
      }
      void pop_back()
      {
        assert(size()>0);
        _finish--;
      }

      void swap(vector<T>& v)
      {
        ::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
      }
      
      iterator insert(iterator pos, const T& val)
      {
        assert(pos >= _start);
        assert(pos <= _finish);
        if(_finish == _end_of_storage)
        {
          size_t len = pos - _start; 
          reverse(capacity() == 0 ? 4 : capacity()*2);
          pos = _start + len;
        }
        iterator end = _finish - 1;
        while(end >= pos)
        {
          *(end + 1) = *end;
          end--;
        }
        *pos = val;
        ++_finish;
        return pos;
      }
     iterator erase(iterator pos)
     {
       assert(pos >= _start);
       assert(pos< _finish);
       iterator end = pos + 1;
       while(end < _finish)
       {
          *(end - 1) = *end;
          ++end;
       }
      --_finish;
      return pos; 
     }
    private:
      T* _start;
      T* _finish;
      T* _end_of_storage;

  };
}
